package com.future;

import java.util.HashSet;
import java.util.Set;

/**
 * Description: 149. 直线上最多的点数
 * 输入：points = [[1,1],[2,2],[3,3]]
 * 输出：3
 * 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出：4
 *
 * @author weiruibai.vendor
 * Date: 2023/1/13 10:40
 */
public class Solution_149 {


    private static Solution_149 instance = new Solution_149();

    public static void main(String[] args) {
        int[][] points = new int[][]{{1, 1}, {2, 2}, {3, 3}};

        // [[-6,-1],[3,1],[12,3]]
        points = new int[][]{{-6, -1}, {3, 1}, {12, 3}};
        // [[0,0],[4,5],[7,8],[8,9],[5,6],[3,4],[1,1]]
        //points = new int[][]{{0, 0}, {4, 5}, {7, 8}, {8, 9}, {5, 6}, {3, 4}, {1, 1}};

        /**
         * 这个用例没过
         * 答案是6
         */
        points = new int[][]{{7, 3}, {19, 19}, {-16, 3}, {13, 17}, {-18, 1}, {-18, -17}, {13, -3}, {3, 7}, {-11, 12}, {7, 19}, {19, -12}, {20, -18}, {-16, -15}, {-10, -15}, {-16, -18}, {-14, -1}, {18, 10}, {-13, 8}, {7, -5}, {-4, -9}, {-11, 2}, {-9, -9}, {-5, -16}, {10, 14}, {-3, 4}, {1, -20}, {2, 16}, {0, 14}, {-14, 5}, {15, -11}, {3, 11}, {11, -10}, {-1, -7}, {16, 7}, {1, -11}, {-8, -3}, {1, -6}, {19, 7}, {3, 6}, {-1, -2}, {7, -3}, {-6, -8}, {7, 1}, {-15, 12}, {-17, 9}, {19, -9}, {1, 0}, {9, -10}, {6, 20}, {-12, -4}, {-16, -17}, {14, 3}, {0, -1}, {-18, 9}, {-15, 15}, {-3, -15}, {-5, 20}, {15, -14}, {9, -17}, {10, -14}, {-7, -11}, {14, 9}, {1, -1}, {15, 12}, {-5, -1}, {-17, -5}, {15, -2}, {-12, 11}, {19, -18}, {8, 7}, {-5, -3}, {-17, -1}, {-18, 13}, {15, -3}, {4, 18}, {-14, -15}, {15, 8}, {-18, -12}, {-15, 19}, {-9, 16}, {-9, 14}, {-12, -14}, {-2, -20}, {-3, -13}, {10, -7}, {-2, -10}, {9, 10}, {-1, 7}, {-17, -6}, {-15, 20}, {5, -17}, {6, -6}, {-11, -8}};
        System.out.println(instance.maxPoints_v2(points));
    }


    /**
     * 用例没跑完！！
     * 思路：y=kx+b
     * 由于计算k和b会失真
     * 所以转成只计算两节点的k
     * 斜率一样，那么就是在同一条线上
     * 并且k记录成(x1-x2)_(y1-y2)（注意，由于2_4和1_2实际上斜率都是1/2，所以为了归结到同一个斜率上，需要除以两个数的最大公约数！）
     *
     * @param points
     * @return
     */
    public int maxPoints_v2(int[][] points) {
        int ans = 0;
        int N = points.length;
        if (N < 3) {
            return N;
        }
        Set<String> hasCalcK = new HashSet<>();
        for (int i = 0; i < N; i++) {
            int tmpAns = 1;
            boolean start = true;
            String curKey = "";
            for (int j = 0; j < N; j++) {
                String key;
                if (i == j) continue;
                // 斜率
                int y = points[j][1] - points[i][1];
                if (y == 0) {
                    /**
                     * 横向与x轴平行的一条直线
                     * eg:(0,3),(1,3),(2,3)
                     */
                    key = "0_" + points[i][1];
                } else {
                    int x = points[j][0] - points[i][0];
                    if (x == 0) {
                        /**
                         * 纵向与y轴平行的一条直线
                         * eg:(0,1),(0,2),(0,3)
                         */
                        key = points[j][0] + "_0";
                    } else {
                        int v = greatestCommonDivisor(x, y);
                        y /= v; // 除以最大公约数
                        x /= v; // 除以最大公约数
                        key = x + "_" + y;
                        if (hasCalcK.contains(key)) continue;
                    }
                }
                if (start) {
                    curKey = key;
                    tmpAns++;
                    start = false;
                } else if (curKey.equals(key)) {
                    tmpAns++;
                }

            }
            hasCalcK.add(curKey);
            ans = Math.max(ans, tmpAns);
        }
        return ans;
    }


    /**
     * eg:
     * a=45 b=35
     * 1、45%35=10
     * 2、35%10=5
     * 3、10%5=0
     * 结果是5
     *
     * @param a
     * @param b
     * @return
     */
    private int greatestCommonDivisor(int a, int b) {
        if (b == 0) {
            return a;
        }
        return greatestCommonDivisor(b, a % b);
    }

    /**
     * 设直线函数：y=kx+b
     * (x1,y1)、(x2,y2)
     * 斜率 k=(y2-y1)/(x2-x1)
     * 1 、计算斜率k (但是计算可能失真!!!)
     * 2、计算常数b (但是计算可能失真!!!)
     * 3、一次看是否在直线上
     *
     * @param points
     * @return
     */
    public int maxPoints(int[][] points) {
        int ans = 0;
        int N = points.length;
        if (N < 3) {
            return N;
        }
        Set<Double> noRepeatK = new HashSet<>();
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                ans = Math.max(getMaxPoints(i, j, points, noRepeatK), ans);
                if (ans == N) {
                    // 如果已经知道在一条直线上的点数等于数组长度，那么就是最大值
                    return ans;
                }
            }
        }
        return ans;
    }


    boolean hasCalcZeroX = false;
    boolean hasCalcZeroY = false;

    private int getMaxPoints(int i, int j, int[][] points, Set<Double> noRepeatK) {
        int res = 0;
        // 斜率
        double y = points[j][1] - points[i][1];
        double x = points[j][0] - points[i][0];
        if (y == 0) {
            if (hasCalcZeroY) return res;
            /**
             * 横向与x轴平行的一条直线
             * eg:(0,3),(1,3),(2,3)
             */
            for (int[] point : points) {
                if (point[1] == points[j][1]) {
                    res++;
                }
            }
            hasCalcZeroY = true;
            return res;
        } else if (x == 0) {
            if (hasCalcZeroX) return res;
            /**
             * 纵向与y轴平行的一条直线
             * eg:(0,1),(0,2),(0,3)
             */
            for (int[] point : points) {
                if (point[0] == points[j][0]) {
                    res++;
                }
            }
            hasCalcZeroX = true;
            return res;
        }
        double k = y / x;
        if (!noRepeatK.add(k)) {
            // 斜率为k的已经计算过了，不需要重复计算
            return res;
        }
        double b = (double) points[j][1] - k * ((double) points[j][0]);
        for (int[] point : points) {
            double val = (y * point[0]) / x + b;
            if (val < 0) {
                // 向下取整
                val = Math.floor(val);
            } else {
                // 向上取整
                val = Math.ceil(val);
            }
            if (point[1] == val) {
                res++;
            }
        }
        return res;
    }

}
